package Euler10;

import java.math.BigInteger;
import java.util.*;

public class PrimeSum {

	public static void main(String[] args) {
		int max = 2000000;
		BigInteger sum = new BigInteger("0");
		List<Integer> primes = GetPrimes(max);
		
		for(int i=0;i<primes.size();i++)
		{
			sum = sum.add(new BigInteger(Integer.toString(primes.get(i))));
		}
		
		System.out.println(sum.toString());
	}

	public static List<Integer> GetPrimes(int max)
	{
		List<Integer> primes = new ArrayList<Integer>();
		int limit = max;
		boolean[] sieve = new boolean[limit + 1];
		int limitSqrt = (int)Math.sqrt((double)limit);
		
		Arrays.fill(sieve, false);

		sieve[0] = false;
		sieve[1] = false;
		sieve[2] = true;
		sieve[3] = true;

		for (int x = 1; x <= limitSqrt; x++) {
		    for (int y = 1; y <= limitSqrt; y++) {
		        // first quadratic using m = 12 and r in R1 = {r : 1, 5}
		        int n = (4 * x * x) + (y * y);
		        if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
		            sieve[n] = !sieve[n];
		        }
		        // second quadratic using m = 12 and r in R2 = {r : 7}
		        n = (3 * x * x) + (y * y);
		        if (n <= limit && (n % 12 == 7)) {
		        	sieve[n] = !sieve[n];
		        }
		        // third quadratic using m = 12 and r in R3 = {r : 11}
		        n = (3 * x * x) - (y * y);
		        if (x > y && n <= limit && (n % 12 == 11)) {
		            sieve[n] = !sieve[n];
		        }     
		    }
		} 
		
		// remove all perfect squares since the quadratic
		// wheel factorization filter removes only some of them
		for (int n = 5; n <= limitSqrt; n++) {
		    if (sieve[n]) {
		        int x = n * n;
		        for (int i = x; i <= limit; i += x) {
		            sieve[i] = false;
		        }
		    } 
		}
		
		// put the primes in a List.
		for (int i = 0; i <= limit; i++) {
			if (sieve[i]){
				primes.add(i);
		    }
		}
		
		return primes;
	}
}
